
#include <iostream>
using namespace std;

enum color
{
	RED,
	BLACK
};

template<class k,class v>
struct RBTreeNode
{
	struct RBTreeNode<k,v>* _parent;
	struct RBTreeNode<k,v>* _left;
	struct RBTreeNode<k,v>* _right;

	pair<k, v> _kv;
	color _col;

	RBTreeNode(const pair<k,v>& kv)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

template<class k, class v>
class RBTree
{
	typedef struct RBTreeNode<k,v> Node;
public:
	bool Insert(const pair<k,v>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv > kv)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (cur->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandpa = parent->_parent;
			Node* uncle = nullptr;
			if (grandpa->_left == parent)
				uncle = grandpa->_right;
			else
				uncle = grandpa->_left;
			
			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandpa->_col = RED;
				cur = grandpa;
				parent = cur->_parent;
			}
			else
			{
				Node* grandpa = parent->_parent;
				if (parent == grandpa->_left && cur == parent->_left)
				{
					RotateL(grandpa);
					grandpa->_col = RED;
					parent->_col = BLACK;
				}
				else if (parent == grandpa->_right && cur == parent->_right)
				{
					RotateR(grandpa);
					grandpa->_col = RED;
					parent->_col = BLACK;
				}
				else if (parent == grandpa->_left && cur == parent->_right)
				{
					RotateL(parent);
					RotateR(grandpa);
					grandpa->_col = RED;
					cur->_col = BLACK;
				}
				else
				{
					RotateR(parent);
					RotateL(grandpa);
					grandpa->_col = RED;
					cur->_col = BLACK;
				}
				break;
			}
		}

		_root->_col = BLACK;
	}

	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* LRChild = cur->_right;
		Node* ancestor = parent->_parent;

		if (LRChild)
		{
			LRChild->_parent = parent;
		}
		cur->_left = parent;
		parent->_parent = cur;
		parent->_right = LRChild;

		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ancestor->_left == parent)
			{
				ancestor->_left = cur;
			}
			else
			{
				ancestor->_right = cur;
			}
			cur->_parent = ancestor;
		}
	}

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* RLChild = cur->_left;
		Node* ancestor = parent->_parent;

		if (RLChild)
		{
			RLChild->_parent = parent;
		}
		parent->_parent = cur;
		parent->_left = RLChild;
		cur->_right = parent;

		if (parent == _root)
		{
			_root = cur;
		}
		else
		{
			if (parent == ancestor->_left)
			{
				ancestor->_left = cur;
			}
			else
			{
				ancestor->_right = cur;
			}
		}
		cur->_parent = ancestor;
	}

private:
	Node* _root=nullptr;
};

int main()
{
	RBTree<int, int> tree;
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	for (auto e : a)
	{
		tree.Insert(std::make_pair(e, e));
	}

	return 0;
}